#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct LinkListNode{
	DataType data;
	struct LinkListNode * next;
}LinkListNode,*ListPtr;

LinkListNode * InitLinkList(int n);
LinkListNode * LinkListReverse_1(LinkListNode * head);
//方法二递归法仅适用于不带头结点的单链表，所以这里没有使用，但仍然写出来供参考
LinkListNode * LinkListReverse_2(LinkListNode * head);
LinkListNode * LinkListReverse_3(LinkListNode * head);
LinkListNode * LinkListReverse_4(LinkListNode * head);
int DisplayLinkList(LinkListNode * head);

int main(){
	int n=9;
	LinkListNode * head;
	head=InitLinkList(n);
	printf("原始的序列：");
	DisplayLinkList(head);
	
	head=LinkListReverse_1(head);
	printf("交换第一次后的序列：");
	DisplayLinkList(head);
	
	head=LinkListReverse_3(head);
	printf("交换第二次后的序列：");
	DisplayLinkList(head);
	
	head=LinkListReverse_4(head);
	printf("交换第三次后的序列：");
	DisplayLinkList(head);
	
	return 0;
}

LinkListNode * InitLinkList(int n){
	LinkListNode * head=(LinkListNode*)malloc(sizeof(LinkListNode));
	if(head==NULL) exit(0);
	head->next=NULL;
	LinkListNode * temp=head;
	for(int i=1;i<=n;i++){
		temp->next=(LinkListNode*)malloc(sizeof(LinkListNode));
		if(temp->next==NULL) exit(0);
		temp=temp->next;
        temp->next=NULL;
        temp->data=i;
	}
	return head;
}
int DisplayLinkList(LinkListNode * head){
	LinkListNode * temp=head->next;
	while(temp!=NULL){
		printf("%d",temp->data);
		temp=temp->next;
	}
	printf("\n");
	return 0;
}
LinkListNode * LinkListReverse_1(LinkListNode * head){
	LinkListNode * cur=head->next;
	LinkListNode * pre=NULL, * nex=NULL;
	while(cur!=NULL){
		nex=cur->next;
		cur->next=pre;
		pre=cur;
		cur=nex;
	}
	head->next=pre;
	return head;
}
LinkListNode * LinkListReverse_2(LinkListNode * head){
	if(head==NULL||head->next==NULL) return head;
	LinkListNode * tail=LinkListReverse_2(head->next);
	head->next->next=head;
	head->next=NULL;
	return tail;
}
LinkListNode * LinkListReverse_3(LinkListNode * head){
	if(head->next==NULL||head->next->next==NULL) return head;
	LinkListNode * list=(LinkListNode*)malloc(sizeof(LinkListNode));
	list->next=NULL;
	LinkListNode * temp;
	while(head->next!=NULL){
		temp=head->next;
		head->next=temp->next;
		temp->next=list->next;
		list->next=temp;
	}
	return list;
}
LinkListNode * LinkListReverse_4(LinkListNode * head){
	LinkListNode * p=head->next, * q=p->next;
	while(q!=NULL){
		p->next=q->next;
		q->next=head->next;
		head->next=q;
		q=p->next;
	}
	return head;
}